//
// Created by liushuai on 2021/1/9.
//

#include "coinChange.h"
int dp(std::vector<int>& coins, int amount,std::vector<int> & cache) {
    if (amount < 0)
        return -1;
    else if(amount == 0)
        return 0;
    else{
        if (cache[amount - 1] != 0)
            return cache[amount - 1];
        else{
            int result = INT_MAX;
            for (int coin:coins) {
                int res = dp(coins, amount - coin,cache);// 选择面额为coin的硬币，意味着结果为 amount-coin的最小硬币是否有解
                if (res >= 0 && res < result) {//如果有解，res>=0，获取不同面额硬币结果，保存最小值
                    result = res + 1;
                }
            }
            // 找到最小值，如果result没有更新过，说明选择面额无法拼凑
            cache[amount - 1] = result == INT_MAX ? -1 : result;
            return cache[amount - 1];
        }

    }

}

int coinChange(std::vector<int>& coins, int amount) {
    std::vector<int> cache = std::vector<int>(amount,0);
    return dp(coins, amount,cache);
}


